package 简单.贪心思想;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 学校的自助午餐提供圆形和方形的三明治，分别用数字 0 和 1 表示。所有学
 * 生站在一个队列里，每个学生要么喜欢圆形的要么喜欢方形的。
 * 餐厅里三明治的数量与学生的数量相同。所有三明治都放在一个 栈 里，每一轮：
 * 如果队列最前面的学生 喜欢 栈顶的三明治，那么会 拿走它 并离开队列。
 * 否则，这名学生会 放弃这个三明治 并回到队列的尾部。
 * 这个过程会一直持续到队列里所有学生都不喜欢栈顶的三明治为止。
 * 给你两个整数数组 students 和 sandwiches ，其中 sandwiches[i] 是栈里面第 i​​
 * 个三明治的类型（i = 0 是栈的顶部）， students[j] 是初始队列里第 j名学生对三明
 * 治的喜好（j = 0 是队列的最开始位置）。请你返回无法吃午餐的学生数量。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/number-of-students-unable-to-eat-lunch
 */
public class 无法吃午餐的学生数量_1700 {

    public static void main(String[] args) {

    }

    /**
     * 栈+模拟
     * 如果所有人都尝试过吃自助餐，如果没有一个人能吃到，则停止循环
     *
     * @param students
     * @param sandwiches
     * @return
     */
    public int countStudents(int[] students, int[] sandwiches) {
        Deque<Integer> queue = new ArrayDeque<>();
        for (int student : students) {
            queue.addLast(student);
        }
        int sandwichIdx = 0;

        while (!queue.isEmpty() && sandwichIdx < sandwiches.length) {
            boolean hasEat = false;
            int size = queue.size();
            while (size-- > 0 && sandwichIdx < sandwiches.length) {
                Integer stu = queue.pollFirst();
                if (stu.equals(sandwiches[sandwichIdx])) {
                    sandwichIdx++;
                    hasEat = true;
                } else {
                    queue.addLast(stu);
                }
            }
            // 这一轮没有人吃到自助餐，下一轮也不可能吃到
            if (!hasEat) {
                return queue.size();
            }
        }

        return queue.size();
    }

    /**
     * 贪心思想
     * 当前所有学生中，没有一个是和栈顶自助餐相匹配的，即为无法吃午餐的学生数量
     * 也就是说餐盘的两种类型的数量大于学生的两种类型的数量，学生就一定能全部
     * 吃到
     *
     * @param students
     * @param sandwiches
     * @return
     */
    public int countStudents1(int[] students, int[] sandwiches) {
        int[] stuType = new int[2];
        for (int student : students) {
            stuType[student]++;
        }

        for (int sandwich : sandwiches) {
            if (stuType[sandwich] <= 0) {
                return stuType[0] + stuType[1];
            }
            stuType[sandwich]--;
        }

        return 0;
    }

}
